package structure.tree;

import java.util.LinkedList;
import java.util.Stack;

/**
 * java实现二叉树遍历
 * 前中后指的是根节点是在前中后那个位置，另外还有一个原则，这三种方式左节点都在右节点前
 * <p>
 * 参考博客：https://mp.weixin.qq.com/s/MlYtcR3I4dlAZuTM1Qo77A
 *
 * @author cuihao
 * @date 2018/2/27
 */
public class BinaryTree {

    private TreeNode rootNode;

    public BinaryTree(int value) {
        rootNode = new TreeNode(value);
        rootNode.left = null;
        rootNode.right = null;
    }

    /**********************************************************************************/


    /**
     * 求最大深度
     */
    public int maxDepth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int left = maxDepth(treeNode.left);
        int right = maxDepth(treeNode.right);
        return Math.max(left, right) + 1;
    }

    /**
     * 求最小深度
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (root.left == null || root.right == null) {
            return left + right + 1;
        }
        return Math.min(left, right) + 1;
    }

    /**
     * 获取全部节点个数
     *
     * @param treeNode
     * @return
     */
    public int numOfTreeNode(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int left = numOfTreeNode(treeNode.left);
        int right = numOfTreeNode(treeNode.right);
        return left + right + 1;
    }

    /**
     * 获取全部子节点的个数
     *
     * @param treeNode
     * @return
     */
    public int numOfNoChildNode(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        if (treeNode.left == null && treeNode.right == null) { // 只有没有左节点和右节点的才算作是子节点，才 + 1
            return 1;
        }
        int left = numOfNoChildNode(treeNode.left);
        int right = numOfNoChildNode(treeNode.right);
        return left + right;
    }


    /**********************************************************************************/


    /**
     * 按值查找
     *
     * @param value
     * @return
     */
    public TreeNode findKey(int value) {
        TreeNode current = rootNode;
        while (true) {
            if (value == current.value) {
                return current;
            }
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            }

            if (current == null) {
                return null;
            }
        }
    }

    /**
     * 按值插入
     *
     * @param value
     * @return
     */
    public String insert(int value) {
        TreeNode node = new TreeNode(value);
        if (rootNode == null) {
            rootNode = node;
        } else {
            TreeNode current = rootNode;
            TreeNode parent = null;
            while (true) {
                if (value < current.value) {
                    parent = current;
                    current = current.left;
                    if (current == null) {
                        parent.left = node;
                        break;
                    }
                } else if (value > current.value) {
                    parent = current;
                    current = current.right;
                    if (current == null) {
                        parent.right = node;
                        break;
                    }
                } else {
                    return null;
                }
            }
        }
        return null;
    }


    /**********************************************************************************/


    /**
     * 类似前序遍历 实际不是（迭代）（广度优先）
     *
     * @param root
     */
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode currentNode = null;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root); // 将根节点入队
        while (!queue.isEmpty()) {
            currentNode = queue.poll(); // queue队列的队头元素出队
            System.out.println(currentNode.value); // 打印当前节点的数据
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }
    }

    /**
     * 前序遍历（迭代）（深度优先）
     *
     * @param node
     */
    public void preDeath(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(node);
        TreeNode treeNode = null;
        while (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.println(treeNode.value);
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            if (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
    }



    /**
     * 前序遍历（递归）
     *
     * @param node
     */
    public void preOrder(TreeNode node) { // 第一个传进来节点的是根节点
        if (node != null) {
            System.out.println(node.value);
            this.preOrder(node.left); // 如果左节点不为空就会一直进行下去
            this.preOrder(node.right);
        }
    }

    /**
     * 中序遍历（递归）
     *
     * @param node
     */
    public void midOrder(TreeNode node) {
        if (node != null) {
            this.midOrder(node.left);// 当左节点为空时,也就是当前节点是最左节点。println将会得到机会第一次执行
            System.out.println(node.value);
            this.midOrder(node.right);
        }
    }

    /**
     * 后序遍历（递归）
     *
     * @param node
     */
    public void lastOrder(TreeNode node) {
        if (node != null) {
            this.lastOrder(node.left);
            this.lastOrder(node.right);
            System.out.println(node.value);
        }
    }

    private class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }

}